public class Offer14 {
    public int cuttingRope(int n) {
        if (n<2){
            return 0;
        }
        if (n==2){
            return 1;
        }
        if (n==3){
            return 2;
        }
        int[] dp = new int[n+1];
        dp[2]=1;
        int max = 0;
        for (int i = 3; i <=n ; i++) {
            for (int j = 1; j <= i/2; j++) {
                dp[i] = Math.max(dp[i],Math.max(i*(i-j),i*dp[i-j]));
            }
        }
        max = dp[n];
        return max;
    }

}
